Traditional communication networks are commonly designed according to a hierarchical architecture. User communication accesses the network via a source node and is routed through dedicated equipment in the network to a destination node. For example, in a wireless communication network including a cellular phone a user may originate a communication session by dialing the telephone number of a desired destination. The user's call is received in a base transceiver station (BTS), where it is typically transferred across a wire line network to the destination. Of course, if the destination is also a wireless remote terminal (e.g., a cellular phone) then the call is routed to a BTS in the cell in which the destination phone resides at the time. The BTS transmits the user communication across the wireless interface to the cellular phone. It will be appreciated that the remote terminals may include data terminals such as, for example, Personal Computers (PC's), Personal Digital Assistants (PDAs), printers, or other terminals capable of transmitting and receiving data packets.
Hierarchical communication networks represent an inefficient use of the radio spectrum in circumstances which the remote terminals are sufficiently close together that they could communicate directly. Establishing a connection through the network requires that two links (e.g., radio channels) be established and consumes resources of at least three radio units (e.g., two remote terminals and a BTS) in the session when only a single link or channel would be required if the terminals could communicate directly with one another. Thus, forcing the communication session through the network reduces the network capacity by at least a factor of two. To make better use of network resources, and thereby improve network efficiency, remote terminals should communicate directly with other terminals, if possible.
Ad-hoc communication networks attempt to address this situation by providing remote terminals with the capability to form direct connections with one another, without the assistance of an intervening communication network. Wireless systems that support ad-hoc connections should provide direct communication among any radio units that are in range of one another. For example, one electronic device (e.g., a desktop PC, a laptop PC, a PDA, a mobile telephone, a printer, a web pad, etc.) should be able to directly communicate with another electronic device (e.g., a desk top PC, laptop PC, mobile telephone, etc.) via radio communication without the need for any other intervening network equipment, as long as the radio transceivers are within range of one another. Such a wireless systems may be used to replace cables or infrared links, e.g., between a computer and a printer, with a short-range radio link (a wireless link) forming a local radio network.
One such ad-hoc communication network recently developed is known as Bluetooth. Bluetooth is a polling based communication infrastructure that may be used for the wireless communication of digital information (e.g., data, voice, video, audio, etc.) between devices using an open specification. Bluetooth may be understood as a wireless personal area network (PAN) technology for short-range transmission of digital information between various electronic devices (e.g., laptops, PDAs, telephones, desktop PCs, printers, facsimiles, etc.) that can interconnect two or more devices in one or more ad-hoc networks. Bluetooth supports point-to-point and multipoint applications and is described in further detail in the Bluetooth Baseband Specification 1.1 by the Bluetooth Special Interest Group (SIG), which is expressly incorporated by reference in its entirety.
The emergence of Bluetooth as a default radio interface in various types of devices provides an opportunity to turn them from stand-alone tools into networked equipment without the need for wired connections or added network devices, such as a BTS, server, router, etc. Bluetooth offers a number of advantages over conventional wireless technologies for communicating between individual electronic devices. For example, unlike conventional infrared data transmission techniques which require line-of-sight between devices, Bluetooth uses omni-directional radio waves that can transmit through walls and other non-metal barriers. Further, infrared communication techniques often were limited to communication between only two devices at a time, requiring a change in the physical alignment of devices for a different pair of devices to communicate. With the use of omni-directional radio and multiplexing of the radio signal, Bluetooth enables communication between more than two electronic devices without changing the physical orientation of the devices. In addition, a device that works in accordance with Bluetooth may also connect in a similar manner to any type of radio communication network, such as cellular networks, satellite or small local radio networks. (See, for example, PCT Published Patent Application WO 00/69186, which is hereby incorporated by reference.) Further, to counteract interference from outside sources or from other devices, Bluetooth units may downgrade the transmission rate instead of halting transmissions altogether. However there are a number of new challenges associated with using Bluetooth technology for ad-hoc network communications, partly stemming from the fact that Bluetooth was originally developed for single hop wireless connections.
Bluetooth systems, in accordance with the Bluetooth Baseband Specification 1.1, use short range radio technology operating in the unlicensed 2.4 GHz Industrial-Scientific-Medical (ISM) band using a frequency hopping scheme. The IEEE 802.11 is another example of a specification utilizing the ISM band. The Bluetooth hopping scheme is performed on 79 RF channels spaced 1 MHz apart using a frequency hopping spread spectrum technique that changes its signal 1600 times per second. A frequency hop transceiver is applied to combat interference and fading. Bluetooth provides considerable data transfer capability at short ranges; e.g., up to approximately 720 Kbps within approximately 10 meters and up to approximately 100 meters with a power boost The Bluetooth system provides full-duplex transmission based on slotted Time Division Duplex (TDD) scheme, where each slot is approximately 0.625 ms long.
An exemplary Bluetooth piconet in its simplest form is shown in FIG. 1. Bluetooth (BT) units are organized into “piconets” which are collections of devices connected in an ad-hoc fashion. Two or more units sharing the same radio channel form a piconet. Bluetooth piconets are “ad-hoc” in that Bluetooth units are free to enter and leave, that is, the piconets are not fixed networks. A piconet is initially formed when two or more devices (e.g., devices 110 and 120) connect via a radio communication transmission, each device herein referred to as “nodes”. One Bluetooth device in each piconet may act as the master, and a master node can have any number of slaves, out of which, for example, up to seven can be active simultaneously, i.e., seven units are able to send and receive data within the piconet if a 3-bit active member address (AM ADDR) is used. In Bluetooth all units are peer units with identical hardware and software interfaces, i.e. being a master or slave is only a logical state. The piconet in the figure has one master node, BT 110 (shown with cross hatching), and one slave node, BT 120. A “master” is the device in a piconet whose clock and hopping sequence are used to sequence other devices in the piconet. A “slave” is any other device in the piconet. The terms “master” and “slave” are defined as logical states, in that a particular Bluetooth device can be a master or a slave. In fact, a Bluetooth unit can simultaneously be a master in one piconet and a slave in one or more other piconets. Any Bluetooth device can become a master, but only one master may exist in a given piconet at one time. It is often the radio unit that initiates the connection that acts as the master unit. Any radio unit may change its role from a slave to a master or a master to a slave.
FIG. 2 illustrates a piconet with a master node 210 and a plurality of slave nodes 220-280 arranged in a star network topology. In a Bluetooth system, a slave node can only communicate directly with its master node. If slave node 220 wishes to communicate with slave node 260, slave node 220 would have to transmit the information it wished to communicate to master node 210. Master node 210 would then transmit the information to slave node 260. Although, as an alternative, the two slaves 220 and 260 could communicate with each other if one of the slaves acts as a master. In addition to being classified as a master node and slave node, a node may be classified as various types of nodes or modes depending on its operation or operating status. For example, a node may be designated an idle node. An idle node is a node which is not currently participating in or connected to a piconet (i.e., not actively connect to any other node in the piconet). Such a node is operating in a “stand by” mode since it is not currently participating in the piconet although it is associated with the piconet. A node that is participating in a piconet is connected to another node in the piconet and would be operating in the active mode. A node that is idle is not connected to any other node in the piconet and is operating in the standby mode. However, if a node is an interpiconet node (i.e., a member of more than one piconet), the node may be currently participating in one of its piconets, while still being connected in all its piconets. A more extensive discussion of various available modes will be provided later.
The communication within a piconet is organized by a master using an intra-piconet scheduling scheme. The master polls each slave according to some polling scheme. Master-to-slave transmissions always start in an even-numbered time slot, while slave-to-master transmissions always start in an odd-numbered time slot. A “frame” includes a pair of corresponding adjacent master-to-slave and slave-to-master slots. A master has frames which are in common with those of its slaves since a master's clock and hopping sequence are used to sequence its slaves. A slave is only allowed to transmit in the current slave-to-master slot if it has been polled by the master in the previous master-to-slave slot. The master may or may not include data in the packet used to poll a slave. Bluetooth packets can be, for example, one, three or five slots long and they can carry synchronous data (e.g., real-time traffic such as voice data) on Synchronous Connection Oriented (SCO) links. Bluetooth packets can also be used to communicate asynchronous data (e.g., elastic data traffic which tend to be less sensitive to delays) on Asynchronous Connectionless (ACL) links. Depending on the type of packet that is used, an acknowledgment and retransmission scheme may be used (typically not for SCO packets transferring synchronous data) to ensure reliable data transfer, as well as forward error correction (FEC) in the form of channel coding.
Each Bluetooth unit (e.g., mobile phone, PC, printer) has a globally unique 48 bit IEEE 802 address. This address, called the Bluetooth Device Address (e.g., BD_ADDR) is initially assigned at the time the Bluetooth unit is manufactured. In addition, the master of a piconet assigns a local active member address (e.g., AM_ADDR) to each active member of the piconet. The AM_ADDR, which is only three bits long, is dynamically assigned and de-assigned and is unique only within a single piconet. The master uses the AM_ADDR when polling a slave in a piconet However, when the slave, triggered by a packet from the master addressed with the slave's AM_ADDR, transmits a packet to the master, it includes: its own AM_ADDR (not the masters) in the packet header.
Several piconets can be established and linked together in an ad-hoc fashion, forming a “scatternet” in which each piconet is characterized by a different frequency hopping sequence. Scatternets are formed when at least one Bluetooth unit participates in more than one piconet at the same time so as to connect multiple independent and unsynchronized piconets having inter-communications. FIG. 3 depicts an exemplary “scatternet” 300 comprising piconet 1 (315), piconet 2 (325) and piconet 3 (335). A Bluetooth unit (master or slave) can participate in (e.g., belong to, or be a member of) more than one piconet at any time, but it can be a master in only one piconet according to the present Bluetooth specification. A unit (or node) that simultaneously belongs, or may belong, to more than one piconet may be referred to as a Participant in Multiple Piconets (PMP) node (e.g., nodes 340 and 380). Since most Bluetooth units have only one transceiver, most PMPs can be active (i.e., be prepared to transmit or receive data) in only one piconet at a single point in time and must switch between piconets on a time division basis. That is, a PMP switches back and forth between piconets to communicate in one or the other, hence abiding by the premise that a Bluetooth unit with a single transceiver can transmit or receive in only one piconet at a single point in time. Thus, a PMP is in an “active mode” in a first piconet if it is prepared to transmit or receive data from a node the first piconet and is necessarily inactive (i.e., not in an “active mode”) in a second piconet in which it is participating.
The piconet 1 (315) of FIG. 3 includes a master node 330, and the slave nodes 310, 320 and 340. The piconet 2 includes the master node 350, and the slave nodes 340, 360, 370 and 380. The piconet 3 includes the master node 390, and the slave nodes 380, 385 and 395. PMP nodes 340 and 380 are used to implement the scatternet shown in the figure. If, for example, node 310 wishes to communicate with node 385, then nodes 340 and 380 might act as bridging nodes by forwarding packets between the two piconets and in particular between nodes 310 and 385. Node 310 transfers the information to node 330, the master node of piconet 1. Master node 330 transmits the information to a PMP forwarding node 340. PMP forwarding node 340 then forwards the information to master node 350, which in turn, transmits the information to PMP forwarding node 380. PMP forwarding node 380 forwards the information to master node 390 which transmits the information to the destination node 385.
As given above, a “scatternet” network includes a set of independent, non-synchronized piconets that are interconnected. Since these different piconets (e.g., 1, 2, and 3) are not typically synchronized in time, a PMP may tend to lose some time when switching from one piconet to another. Furthermore, the temporal unavailability of PMP nodes must be taken into account when coordinating the communication with them. The inefficiencies of switching between piconets to communicate with a PMP present a significant constraint in building scatternets.
A Bluetooth unit participating in multiple piconets (a PMP node) does so on a time division basis. Hence, its presence in the different piconets must be controlled by some scheduling mechanism. Such scheduling is denoted inter-piconet scheduling as opposed to intra-piconet scheduling which is a mechanism controlling the master's polling of its slaves.
Inter-piconet scheduling is one area of difficulty for Bluetooth. Due to the need to synchronize its radio from one piconet to another, a Bluetooth unit necessarily loses some time while switching, which represents an important performance constraint in scheduling the scatternet. Furthermore, the temporal unavailability of PMP nodes must be taken into account when coordinating the communication with them. The inefficiencies of inter-piconet communication present a significant constraint in building scatternets.
There are two effects that can significantly reduce the efficiency of the polling based communication in Bluetooth scatternets. First, nodes that have no data to transmit may be unnecessarily polled, while other nodes with data to transmit may have to wait to be polled. Second, at the time of an expected poll one of the nodes of a communicating node pair may not be present in the piconet. For example, the slave that is being polled may not be listening, or the slave expecting to be polled is not polled by its master. Both situations give rise to inefficiencies in carrying out communications.
One primary problem in inter-piconet communication arises in trying to effectively coordinate the presence of PMP nodes in different piconets such that the occurrence of timing conflicts is minimized. A conflict occurs if a PMP node is assumed to be active by one or more of those piconets it participates in, but the PMP node is not active in the piconets or otherwise unavailable. It can be equivalently disadvantageous if the PMP node is active in one of the piconets that assumes the PMP node to be inactive at that time. Further, the pre-scheduling and the intra-piconet communication may cause inefficiencies and should also be considered.
The timing of reaction time is a common idealization which does not always reflect real-world conditions. For instance, designs of Bluetooth scheduling algorithms often assume that the scheduler reacts in frame f(n+1) to occurrences in frame f(n). However, due to the non-ideal nature of electronic hardware, it is often not possible to react that fast. In effect, what happens in frame f(n) will generally not affect the schedule until k frames later, i.e., frame f(n+k), where k>>1. Such delay can, for example, be introduced by batched scheduling. Batched scheduling means that instead of scheduling frames one by one in a continuous flow, a schedule is computed for a number of frames; e.g., a batch of frames is scheduled all at once. While one batch is being executed the next batch is computed. Since the frames are batched for execution rather than continuously scheduling them, a delay is introduced which leads to inefficiencies in the system.
The fundamental building block in Bluetooth is the piconet which requires intra-piconet scheduling. One system for intra-piconet scheduling is the Fair Exhaustive Polling system (FEP). Such schedulers divide the capacity within the piconet according to the dynamic bandwidth demands of the traffic. For example, the master of the piconet may poll only slaves it considers to be in the “active” mode. These slaves are put into an “active group”. Note that inactive nodes may be nodes that are PMPs in other networks or simply nodes that do not have data to send or receive. The nodes in the active group may be scheduled to, for example, a round robin scheduling scheme or a weighted priority scheduling scheme to establish the particular times when data may be shared between the various slaves and master. Transition between the active and inactive groups may be made, for example, in the following manner: inactive nodes are polled periodically to see if they now have data to send. Active nodes may become in-active if they have no data to receive or send for a number of polls.
Regardless of the workings of intra-piconet scheduling, inter-piconet scheduling is still needed to enable devices to simultaneously participate in multiple piconets. In fact, even PMP devices with inter-piconet scheduling capabilities have most of their communication traffic occurring within one piconet such that large portions of the PMP Bluetooth device's time will be as member of one piconet. Thus, the importance of efficient intra-piconet scheduling will not decrease when inter-piconet scheduling is introduced and the inter-piconet scheduler must not deteriorate the efficiency of the intra-piconet scheduler. Ideally, the inter-piconet scheduler should work integrally with the intra-piconet scheduler to provide the overall scatternet communication efficiency. One attempt at providing an efficient inter-piconet scheduler was proposed in previous U.S. patent application Ser. No. 09/454,758, filed Dec. 6, 1999, hereby incorporated by reference for all purposes. However, a more flexible approach as proposed by the present invention provides even better overall scatternet scheduling efficiency.